/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package cs;

import java.util.Scanner;

/**
 *
 * @author QuangHieu
 */
class Node {

    int data;
    Node next;

    Node(int x) {
        data = x;
        next = null;
    }

    Node(int x, Node t) {
        data = x;
        next = t;
    }
}

public class MySingleList {

    Node head, tail;

    public MySingleList() {
        head = tail = null;
    }

    void append(int x) {
        Node t = new Node(x);
        if (head == null) {
            head = tail = t;
        } else {
            tail.next = t;
            tail = t;
        }
    }

    void taoDS() {
        head = tail = null;
        int x, i = 1;
        Scanner kb = new Scanner(System.in);
        while (true) {
            System.out.print("\nNhap so thu " + (i++) + ":");
            x = kb.nextInt();
            if (x != 0) {
                append(x);
            } else {
                break;
            }
        }

    }

    void them(int x, int k) {
        int i = 1;
        Node t = new Node(x);

        if (k < 1) {
            System.out.print("Khong chen duoc");
            return;
        } else if (k == 1) {
            t.next = head;
            head = t;
        } else {
            Node nodeRef = head;
            while (i < k && nodeRef != null) {
                nodeRef = nodeRef.next;
                i++;
            }
            if (i == k) {
                t.next = nodeRef.next;
                nodeRef.next = t;
            } else {
                tail.next = t;
                tail = t;
            }
        }
    }

    void xoa(int k) {
        if (k < 1) {
            System.out.print("Khong xoa duoc");
            return;
        }
        int i = 1;
        Node nodeRef = head;
        while (i < k && nodeRef != null) {
            nodeRef = nodeRef.next;
            i++;
        }
        if (i == k) {
            Node t = nodeRef.next;
            nodeRef.next = nodeRef.next.next;
            t.next = null;
        } else {
            System.out.print("Vi tri vuot qua spt ds!");
        }
    }

    boolean kiemTraDoiXung() {

        Node nodeRef = head;
        Node t=tail;
        while (nodeRef != t) {
            if (nodeRef.data != t.data) {
                return false;
            }
            Node p = head;
            while (p.next != t) {
                p = p.next;
            }
            if(nodeRef.next!=t){
                nodeRef = nodeRef.next;
                t = p;
            }
            else
                return true;
        }
        return true;
    }

    @Override
    public String toString() {
        String t = "==>";
        Node p = head;
        while (p != null) {
            t = t + p.data + "==>";
            p = p.next;
        }
        t = t + "null";
        return t;
    }

    public static void main(String[] agrs) {
        MySingleList l = new MySingleList();
        l.taoDS();
        System.out.print("\nDanh sach vua tao:\n" + l);
        //l.append(100);
        //System.out.print("\nDanh sach sau khi them 100:\n"+l+"\n");
        //l.them(50, 4);
        //System.out.print("\nDanh sach sau kh1i them :\n"+l+"\n");
        //l.xoa(4);
        //System.out.print("\nDanh sach sau khi xoa :\n"+l+"\n");
        if(l.kiemTraDoiXung())
            System.out.print("Doi Xung\n");
        else
            System.out.print("Khong Doi Xung\n");
    }
}
